package com.lfg.nc;

public class NC127 {

    public static void main(String[] args) {
        System.out.println(LCS("d8Wt20lnSgAw0HgauN2Kspyr298H6wQWMO3tMNRpWmR25NNTD4VTnq16LX80khSMEG0W5V72cIDLvy0WB1Nfnz4z51qrGNKT3xImT141NY92514w8AF5q1sul7MVNFZnGengc03vO912lFftHDkWpMwWN0SY4pXO1QLji18ujkZV4vr449Wo495WOyIXiO4C9M5L7hQ4tX9ePvV5ohnX00e4mOW28xO968cdR266Ej5M"
                , "MV3Et2Q4x4YFlN304p5oLJzVT5zdfz8X83srj64mAx18Ai8kE82aF4so17uR3tD7Nch9CO775WHeVD166zgogKQAj4y04EjJ6Mc23Uvmt11NY92514w8AF5q1sul7MVNFZndJq1vh7qx45XOwP1k1M9jsbB3MLc9FFoy825lu0Cs9Bh3Xm84p5C36r6USQrF96W0b05RfF308001LpK89056qQ8517YFj4pM"));
    }

    /**
     * longest common substring
     *
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public static String LCS(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] matchLength = new int[m+1][n+1];

        int maxLastIndex = 0;
        int length = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n ; j++) {
                if (str1.charAt(i) == str2.charAt(j)) {
                   matchLength[i+1][j+1] = matchLength[i][j]+1;
                   if(matchLength[i+1][j+1]> length){
                       length = matchLength[i+1][j+1];
                       maxLastIndex = i;
                   }
                   if(matchLength[i+1][j+1] == m || matchLength[i+1][j+1] == n){
                       break;
                   }
                } else {
                    matchLength[i+1][j+1] = 0;
                }
            }
        }
        return str1.substring(maxLastIndex-length+1, maxLastIndex+1);
    }
}
